#ifndef RECURSION_H_
#define RECURSION_H_

#include "sort.hpp"
#include <algorithm>
#include <cstddef>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

namespace
{
inline void sub(const std::string&               str,
                int                              i,
                std::string&                     path,
                std::unordered_set<std::string>& set)
{
    if (i == str.size()) {
        set.insert(path);
    }
    else {
        path.push_back(str[i]);
        sub(str, i + 1, path, set);
        path.pop_back();
        sub(str, i + 1, path, set);
    }
}

inline void subWithDup(const std::vector<int>&        nums,
                       int                            i,
                       std::vector<int>&              path,
                       int                            size,
                       std::vector<std::vector<int>>& vvi)
{
    if (i == nums.size()) {
        std::vector<int> cur(size);
        std::copy(path.begin(), path.begin() + size, cur.begin());
        vvi.push_back(cur);
    }
    else {
        int j = i + 1;
        while (j < nums.size() && nums[j] == nums[i]) {
            j++;
        }
        subWithDup(nums, j, path, size, vvi);
        for (; i < j; i++) {
            path[size++] = nums[i];
            subWithDup(nums, j, path, size, vvi);
        }
    }
}

template<class Func>
inline void do_permute(std::vector<int>& nums, int i, std::vector<std::vector<int>>& ans, Func swap)
{
    if (i == nums.size()) {
        ans.push_back(nums);
    }
    else {
        std::unordered_set<int> set;
        for (int j = i; j < nums.size(); j++) {
            if (set.count(nums[j]) != 0) continue;
            set.insert(nums[j]);
            swap(nums, i, j);
            do_permute(nums, i + 1, ans, swap);
            swap(nums, i, j);
        }
    }
}

inline int bottom_out(std::stack<int>& stack)
{
    int ans = stack.top();
    stack.pop();
    if (stack.empty()) {
        return ans;
    }
    else {
        int last = bottom_out(stack);
        stack.push(ans);
        return last;
    }
}

// 返回栈的深度，不改变栈的数据状况
inline int deep(std::stack<int>& stack)
{
    int top = stack.top();
    stack.pop();
    if (stack.empty()) {
        stack.push(top);
        return 1;
    }
    else {
        int d = deep(stack);
        stack.push(top);
        return d + 1;
    }
}

// 返回此时栈中的最大值，也不改变栈的数据状况
inline int max(std::stack<int>& stack, int deep)
{
    if (deep == 0) return 1 << 31;
    int top = stack.top();
    stack.pop();
    int m = std::max(::max(stack, deep - 1), top);
    stack.push(top);
    return m;
}

// 返回此时栈中的最大值的出现次数，也不改变栈的数据状况
inline int times(std::stack<int>& stack, int deep, int max)
{
    if (deep == 0) return 0;
    int top = stack.top();
    stack.pop();
    int t = max == top ? 1 : 0;
    t += times(stack, deep - 1, max);
    stack.push(top);
    return t;
}

// 将栈中最大值沉底，其它数据相对次序不变
inline void down(std::stack<int>& stack, int deep, int max, int times)
{
    if (deep == 0) {
        while (times--) {
            stack.push(max);
        }
        return;
    }
    else {
        int top = stack.top();
        stack.pop();
        down(stack, deep - 1, max, times);
        if (top == max) return;
        stack.push(top);
    }
}

inline void do_hanota(size_t n, std::vector<int>& A, std::vector<int>& C, std::vector<int>& B)
{
    if (n == 1) {
        C.push_back(A.back());
        A.pop_back();
        return;
    }
    else {
        do_hanota(n - 1, A, B, C);
        C.push_back(A.back());
        A.pop_back();
        do_hanota(n - 1, B, C, A);
    }
}
}   // namespace

namespace lxj
{
// 字符串全部子序列,要求去重
inline std::vector<std::string> subsets(const std::string& str)
{
    std::vector<std::string> vs;
    if (str.empty()) return vs;

    std::unordered_set<std::string> set;
    std::string                     path;
    sub(str, 0, path, set);
    vs.reserve(set.size());
    for (auto& s : set) {
        vs.emplace_back(s);
    }
    return vs;
}

// 力扣90. 子集 II
// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 （幂集）
inline std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums)
{
    std::vector<std::vector<int>> vvi;
    lxj::radix_sort(nums.data(), nums.size());
    std::vector<int> path(nums.size());
    subWithDup(nums, 0, path, 0, vvi);

    return vvi;
}

// 力扣46. 全排列
inline std::vector<std::vector<int>> permute(std::vector<int>& nums)
{
    auto swap = [](std::vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j]  = temp;
    };
    std::vector<std::vector<int>> ans;
    do_permute(nums, 0, ans, swap);
    return ans;
}

// 用递归逆序一个栈
inline void reverse(std::stack<int>& stack)
{
    if (stack.empty()) return;

    int num = bottom_out(stack);
    reverse(stack);
    stack.push(num);
}

// 用递归排序一个栈
inline void sort_by_recursion(std::stack<int>& stack)
{
    int deep = ::deep(stack);
    while (deep > 0) {
        int max = ::max(stack, deep);
        int k   = ::times(stack, deep, max);
        down(stack, deep, max, k);
        deep -= k;
    }
}

// 力扣面试题 08.06. 汉诺塔问题
inline void hanota(std::vector<int>& A, std::vector<int>& B, std::vector<int>& C)
{
    size_t size = A.size();
    if (size > 0) do_hanota(size, A, C, B);
}
}   // namespace lxj

#endif